#include <bits/stdc++.h>

using namespace std;
const int N = 1e5 + 5;//??为什么要定义1e5步应该是100吗

int m, n, w[N],h[N],t[N];
void solve(int i, int &W, int &H)//用于计算放置第i个矩形后的高度和宽度，其中w表示当前宽度，H表示当前高度。根据当前宽度是否能容纳下第i个矩形，更新高度和宽度
{ 
    if(W + w[i] <= m) H = max(H, h[i]);
    else H =  max(H, (h[i] * (m - W) + w[i] - 1) / w[i]);//参考题目中2的情况（4*9->2*5）
    W = min(m, W + w[i]);
}
int calc(int i,int W,int H)//从第i个矩形开始放置，直到宽度达到m时的高度总和
{
    while(i < n && W < m) solve(i ++, W, H);
    return H + t[i];
}
int main()
{
    cin.tie(0);//表示将cin和count的关联关系解除
	ios::sync_with_stdio(0);//关闭输入输出流的同步，提高输入输出的效率
	//关闭同步后，C++的输入输出流不再与C标准输入输出流相关联，而是使用自己的缓冲区，从而提高程序的运行效率
	//没有这两句也能运行成功
    cin >> m >> n;
    for(int i = 0 ; i < n ; i ++ ) cin >> w[i] >> h[i];
    for(int i = n - 1 ; i >= 0 ; i -- ) t[i] = calc(i, 0, 0);//通过循环计算每个矩形放置后的高度总和，并存储再数组t中

    int res = t[0], pre_h = 0, W = 0, H = 0;
    for(int i = 0 ; i < n ; i ++ )//尝试不同的排列方式，找到高度总和最小的情况，并输出最终结果
    {
        int tmp = calc(i + 1, W, H);
        res = min(res, pre_h + tmp);//寻找高度总和最小的情况
        solve(i, W, H);
        if(W == m) pre_h += H, W = 0, H = 0;
    }
    cout << res << endl;
    return 0;
}